#include "countSort.h"
void countSort(int *a, int *b, int n) {
  int maxValue = 0;
  for (int i = 0; i < n; i++) {
    if (a[i] > maxValue)
      maxValue = a[i];
  }
  int *count = new int[maxValue + 1]();
  //   统计元素的频率
  for (int i = 0; i < n; i++) {
    count[a[i]] += 1;
  }
  // 统计小于指定值出现的次数
  for (int i = 1; i <= maxValue; i++) {
    count[i] += count[i - 1];
  }
  for (int i = n - 1; i >= 0; i--) {
    b[count[a[i]] - 1] = a[i];
    count[a[i]] -= 1;
  }
  delete[] count;
}